package com.mlamp.广度优先遍历算法;

import java.util.LinkedList;
import java.util.Queue;

public class 填充每个节点的下一个右侧节点指针 {

    public static void main(String[] args) {
        填充每个节点的下一个右侧节点指针 instance = new 填充每个节点的下一个右侧节点指针();
        Node root = new Node(1);
        Node n2 = new Node(2, new Node(4), new Node(5), null);

        Node n3 = new Node(3, new Node(6), new Node(7), null);
        root.left = n2;
        root.right = n3;
        Node connect = instance.connect(root);
    }


    private static final class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }


    public Node connect(Node root) {
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()) {
            int size = nodes.size();
            Node curNode = null;
            for (int index = 0; index < size; index++) {
                Node poll = nodes.poll();
                if (curNode == null) {
                    curNode = poll;
                    poll.next = null;
                } else {
                    curNode.next = poll;
                    curNode = poll;
                }
                if (poll.left != null) {
                    nodes.add(poll.left);
                }
                if (poll.right != null) {
                    nodes.add(poll.right);
                }
            }
        }
        return root;
    }


}
